package com.explorati.dongtaiguihua.LeetCode198.HouseRobber;

import java.util.Arrays;

/**
 * 198. House Robber
 * 
 * 暴力解法：检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值。找最大值.O((2^n)*n)
 * 
 * 动态规划解法
 * 
 * @author explorati
 *
 */
public class Solution1 {

	public static int rob(int[] nums) {
		int n = nums.length;
		if (n == 0) {
			return 0;
		}

		// memo[i]表示考虑抢劫nums[i...n - 1]所能获得的最大收益
		int[] memo = new int[n];
		Arrays.fill(memo, -1);

		memo[n - 1] = nums[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			for (int j = i; j < n; j++) {
				memo[i] = Math.max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0));
			}
		}
		return memo[0];
	}
}
